package arithmetic;

import java.util.Arrays;

public class OrderTest {

    public static void main(String[] args) {
        System.out.println("---------------------------------------------");
        int[] nums = {2990, 22, 12, 33, 22, 1, 4, 34, -1, 13, 554, 553, 25, 23, 4, 5, 233, 2, 3, 2, 3};
        int[] clone = nums.clone();
        int[] is = bubbleOrder(nums);
        System.out.println("排序之前：");
        System.out.println(Arrays.toString(clone));
        System.out.println("排序之后：");
        System.out.println(Arrays.toString(is));
    }

    /**
     * 插入排序思想： 插入排序，顾名思义，就是通过直接插入的方式排序，假定在待待排序的元素中，前面N个元素是排好序的，
     * 现在将第N个元素插入待排好序的某个位置，似的这N个元素都是排好序的
     *
     * @return 返回已经排序的数组集合  8 3   6   2
     * 插入排序 ：背都要背下来
     * 时间复杂度最坏为O(n^2)，最好为O(n)。
     */
    public static int[] insert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (int j = i - 1; j >= 0 && arr[j] > temp; j--) {
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
        return arr;
    }

    /**
     * 冒泡排序  主要思想：元素就像冒泡一样升起来，本质是循环遍历，每次相邻两个元素进行交换，一次循序就像最大的元素找到。
     *
     * @param nums 5  23  6  2   3  44  112  43
     * @return
     */
    public static int[] bubbleOrder(int[] nums) {
        if (nums.length > 0) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums.length-i-1 ; j++) {
                    if(nums[j]>nums[j+1]){
                        int temp=nums[j+1];
                        nums[j+1]=nums[j];
                        nums[j]=temp;
                    }
                }

            }
        }
        return nums;
    }


    /**
     * 选择排序 和冒泡排序的区别是：选择排序是一次循环获取最小值的下标 ，然后只执行一次交换
     * 冒泡排序是次次都要交换  时间复杂度应该是一样  都是O(N2)
     *
     * @param nums 5  23  6  2   3  44  112  43
     * @return
     */
    public static Integer[] chooseOrder(Integer[] nums) {
        if (nums.length > 0) {
            for (int i = 0; i < nums.length - 1; i++) {
                int small = i;
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[small] > nums[j]) {
                        small = j;
                    }
                }
                if (small != i) {
                    int temp = nums[i];
                    nums[i] = nums[small];
                    nums[small] = temp;
                }
            }
        }
        return nums;
    }


    /**
     * 希尔排序:是一种插入排序的缩小增量排序，是插入排序的一种更高级的改进版本。
     * 本质是一种分组插入方法。设定一个步长，然后步长内的元素两两交换
     *
     * @return
     */
    public static Integer[] SheelOrder(Integer[] nums) {
        int step = nums.length;

        while (step > 1) {
            step = step / 3 + 1;

            for (int i = step; i < nums.length; i++) {

                int k = nums[i];//当前比较的元素

                int end = i - step;//头元素

                while (end >= 0 && nums[end] > k) {

                    nums[end + step] = nums[end];

                    end -= step;

                }
                nums[end + step] = k;

            }
        }
        return nums;
    }


    public static int singleNumber(Integer[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }
        for (int i = 0; i < nums.length; i++) {
            int k = nums[i];
            boolean blage = true;
            for (int j = 0; j < nums.length; j++) {
                if (j != i && k == nums[j]) {
                    blage = false;
                    break;
                }
            }
            if (blage) {

                return k;
            }
        }
        return 0;
    }
}
